#!/bin/bash
VERSION="0.9"

## Simple Bash implementation of Conway's Game of Life
##
## this zero player game runs by itself without any need of control. just start
## the script. it uses the glider as a default pattern. if you want to add your
## own pattern, create a text file (20 lines, 60 chars per line) using dots (.)
## for dead cells and the character X for alive cells. see *.gol files for some
## examples. the game basics are (c) 1970 by John Conway. for more informations
## about the game visit http://www.wikipedia.org/wiki/Conway%27s_Game_of_Life
##
## very very special thanks to the people who helped me making this project:
## Michael Butschek for bash teaching, testing, so many ideas & so many more
## Mathias Habluetzel for git skills, mac testing, being such a geek xD
##
## Copyright (c) 2011 by Justin Keil <JustinTheFreak@GoogleMail.com>
## Version: 0.9
## Depends: bash(>= 3.2)
##
## Project Homepage: http://conways-game-of-life-bash.googlecode.com/
##
## This program is free software: you can redistribute it and/or modify it under
## the terms of the GNU General Public License as published by the Free Software
## Foundation, either version 3 of the License, or (at your option) any later
## version.
##
## This program is distributed in the hope that it will be useful, but WITHOUT
## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
## FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
## details.
##
## You can received a copy of the GNU General Public License at this URL:
## http://www.gnu.org/licenses/


# -----------------------------------------------------------------------------
# initialize variables
# -----------------------------------------------------------------------------

  FIELD_ROWS=60
  FIELD_LINES=20

  AUTOADJUST=0
  USEANSICOLOR=1
  LOOPPROTECTION=1
  MAXITERATIONS=1000

  SAVEFILE=''
  SAVEFILEDELAY='0.1s'

  DO_RANDOM_FIELD="no"


# -----------------------------------------------------------------------------
# get shell options
# -----------------------------------------------------------------------------

  while [ "${1:0:1}" == '-' ]
    do
    case "$1" in
      -a|--adjust)
        AUTOADJUST=1
        shift
        ;;
      -d|--delay)
        SAVEFILEDELAY="$2"
        shift
        shift
        ;;
      -h|--help)
         echo "Conway's Game of Life Bash v${VERSION}"
         echo "Simple Bash implementation of Conway's Game of Life"
         echo
         echo "Usage: $0 [OPTION]... [FILE]"
         echo
         echo "  -h, --help               print this help screen"
         echo "  -v, --version            show version"
         echo
         echo "  -x, --rows               size of field rows. default: 60"
         echo "  -y, --lines              size of field lines. default: 20"
         echo
         echo "  -a, --adjust             adjust field when a border is touched"
         echo "  -i, --iterations [num]   iteration count till exit. default: 1000"
         echo "  -l, --loop               disable oscillator detection, allow loops"
         echo "  -n, --nocolor            don't use ansi escape sequences"
         echo
         echo "  -s, --save [file]        file to save the game as a bash player"
         echo "                           replay it later using: bash [file]"
         echo "  -d, --delay [time]       delay time for save files. default: 0.1s"
         echo
         echo "  -r, --random [percent]   create a random field, percent = [0-100]"
        exit 0
        ;;
      -i|--iterations)
        MAXITERATIONS="$2"
        shift
        shift
        ;;
      -l|--loop)
        LOOPPROTECTION=0
        shift
        ;;
      -n|--nocolor)
        USEANSICOLOR=0
        shift
        ;;
      -r|--random)
        DO_RANDOM_FIELD=$2
        shift
        shift
        ;;
      -s|--save)
        SAVEFILE="$2"
        if [ -e "$SAVEFILE" ]
          then
          echo "savefile still exists: '$SAVEFILE'"
          exit 1
          fi
        shift
        shift
        ;;
      -v|--version)
        echo "Conway's Game of Life Bash v${VERSION}"
        exit 0
        ;;
      -x|--rows)
        FIELD_ROWS="$2"
        shift
        shift
        ;;
      -y|--lines)
        FIELD_LINES="$2"
        shift
        shift
        ;;
      *)
        echo "Invalid option: '$1'"
        echo 'Try `'$0' --help` for more information.'
        exit 1
        ;;
      esac
    done


# -----------------------------------------------------------------------------
# create random field
# -----------------------------------------------------------------------------

  if [[ "$DO_RANDOM_FIELD" != 'no' ]]
    then
    for LINE in $(seq 1 $FIELD_LINES)
      do
      for ROW in $(seq 1 $FIELD_ROWS)
        do
          if [ $(($RANDOM%100)) -lt $DO_RANDOM_FIELD ]
            then
            echo -n 'X'
            else
            echo -n '.';
            fi
        done
      echo
      done
    exit 0
    fi


# -----------------------------------------------------------------------------
# create temporary files
# -----------------------------------------------------------------------------

  umask 0066
  TEMPFILE=$(mktemp -t gol-XXXXXXXX.tmp)
  if [[ "$TEMPFILE" == "" ]]; then echo "Error: mktemp did not work."; exit 1; fi
  TEMPFILE2=$(mktemp -t gol-XXXXXXXX.tmp)
  if [[ "$TEMPFILE2" == "" ]]; then echo "Error: mktemp did not work."; exit 1; fi
  trap "rm -f $TEMPFILE $TEMPFILE2" EXIT


# -----------------------------------------------------------------------------
# load pattern file
# -----------------------------------------------------------------------------

# load pattern file

  if [[ "$1" == '' ]]
    then
    echo 'Error: No pattern file given.'
    echo 'Try `'$0' --help` for more information.'
    exit 1
    fi

  if [ ! -r "$1" ]
    then
    echo "Error: Unable to open file: '$1'"
    echo 'Try `'$0' --help` for more information.'
    exit 1
    fi

  cat "$1" > $TEMPFILE

  while [ `cat $TEMPFILE | wc -l` -lt $FIELD_LINES ]
    do
    ( echo; cat $TEMPFILE; echo ) > $TEMPFILE2
    cat $TEMPFILE2 > $TEMPFILE
    done

  cat $TEMPFILE \
    | awk '{WIDTH='$FIELD_ROWS'; LINE=$1; while (length($LINE)<WIDTH) $LINE="."$LINE"."; print substr($LINE, 0, WIDTH+1) }' \
    > $TEMPFILE2

  cat $TEMPFILE2 | head -n $FIELD_LINES > $TEMPFILE

# -----------------------------------------------------------------------------
# adjust functions
# -----------------------------------------------------------------------------

  function adjust
    {

    LINE_FIRST=${DATA[0]}
    LINE_SECOND=${DATA[1]}
    LINE_SECONDLAST=${DATA[$[$FIELD_LINES-2]]}
    LINE_LAST=${DATA[$[$FIELD_LINES-1]]}

    ROW_FIRST=$(for LINE in $(seq 1 $FIELD_LINES); do echo -n ${DATA[$[$LINE-1]]:0:1}; done )
    ROW_SECOND=$(for LINE in $(seq 1 $FIELD_LINES); do echo -n ${DATA[$[$LINE-1]]:1:1}; done )
    ROW_SECONDLAST=$(for LINE in $(seq 1 $FIELD_LINES); do echo -n ${DATA[$[$LINE-1]]:$[${FIELD_ROWS}-2]:1}; done )
    ROW_LAST=$(for LINE in $(seq 1 $FIELD_LINES); do echo -n ${DATA[$[$LINE-1]]:$[${FIELD_ROWS}-1]:1}; done )

    # last line not empty: move up
    if [[ "$LINE_FIRST" =~ ^[\.]+$ ]] && [[ "$LINE_SECOND" =~ ^[\.]+$ ]] && [[ ! "$LINE_LAST" =~ ^[\.]+$ ]]
      then
      TEMPLINE=${DATA[0]}
      for LINE in $(seq 1 $FIELD_LINES); do DATA[$[$LINE-1]]=${DATA[$LINE]}; done
      DATA[$[$FIELD_LINES-1]]=$TEMPLINE
      fi

    # first line not empty: move down
    if [[ "$LINE_LAST" =~ ^[\.]+$ ]] && [[ "$LINE_SECONDLAST" =~ ^[\.]+$ ]] && [[ ! "$LINE_FIRST" =~ ^[\.]+$ ]]
      then
      TEMPLINE=${DATA[$[$FIELD_LINES-1]]}
      for LINE in $(seq $FIELD_LINES -1 1); do DATA[$LINE]=${DATA[$[$LINE-1]]}; done
      DATA[0]=$TEMPLINE
      fi

    # last row not empty: move left
    if [[ "$ROW_FIRST" =~ ^[\.]+$ ]] && [[ "$ROW_SECOND" =~ ^[\.]+$ ]] && [[ ! "$ROW_LAST" =~ ^[\.]+$ ]]
      then
      for LINE in $(seq 1 $FIELD_LINES)
        do
        DATA[$[$LINE-1]]=${DATA[$[$LINE-1]]:1}'.'
        done
      fi

    # first row not empty: move right
    if [[ "$ROW_LAST" =~ ^[\.]+$ ]] && [[ "$ROW_SECONDLAST" =~ ^[\.]+$ ]] && [[ ! "$ROW_FIRST" =~ ^[\.]+$ ]]
      then
      for LINE in $(seq 1 $FIELD_LINES)
        do
        TEMPLINE=${DATA[$[$LINE-1]]}
        TEMPLINE=${TEMPLINE:0:$[${#TEMPLINE}-1]}
        DATA[$[$LINE-1]]='.'$TEMPLINE
        done
      fi

    echo
    }


# -----------------------------------------------------------------------------
# game of life functions
# -----------------------------------------------------------------------------

  # get a single pixel (0 or 1) of the matrix in $data
  function get_pixel() # [$1:row] [$2:line]
    {
    if [ $1 -ge 1 ] && [ $2 -ge 1 ] && [[ "${DATA[$[$2-1]]:$[$1-1]:1}" == 'X' ]]
      then return 1
      else return 0
      fi
    }

  # print out the next iteration by checking every pixel row by row, line by line
  function print_next_iteration()
    {
    DATA=( $(cat) )
    if [ $AUTOADJUST -eq 1 ]; then adjust >&2; fi

    for LINE in $(seq 1 $FIELD_LINES)
      do
      for ROW in $(seq 1 $FIELD_ROWS)
        do
        get_pixel $[$ROW-1] $[$LINE-1]; ALIVENEIGHBOURS=$?
        get_pixel $[$ROW-1] $[$LINE+0]; ALIVENEIGHBOURS=$[$ALIVENEIGHBOURS+$?]
        get_pixel $[$ROW-1] $[$LINE+1]; ALIVENEIGHBOURS=$[$ALIVENEIGHBOURS+$?]
        get_pixel $[$ROW+0] $[$LINE-1]; ALIVENEIGHBOURS=$[$ALIVENEIGHBOURS+$?]
        get_pixel $[$ROW+0] $[$LINE+0]; ALIVE=$?
        get_pixel $[$ROW+0] $[$LINE+1]; ALIVENEIGHBOURS=$[$ALIVENEIGHBOURS+$?]
        get_pixel $[$ROW+1] $[$LINE-1]; ALIVENEIGHBOURS=$[$ALIVENEIGHBOURS+$?]
        get_pixel $[$ROW+1] $[$LINE+0]; ALIVENEIGHBOURS=$[$ALIVENEIGHBOURS+$?]
        get_pixel $[$ROW+1] $[$LINE+1]; ALIVENEIGHBOURS=$[$ALIVENEIGHBOURS+$?]

        # alive rules
        CHAR='.'
        if [ $ALIVE -eq 1 ] && [ $ALIVENEIGHBOURS -eq 2 ]; then CHAR='X'; fi
        if [ $ALIVENEIGHBOURS -eq 3 ]; then CHAR='X'; fi

        echo -n "$CHAR"
        done
      echo
      done
    }


# -----------------------------------------------------------------------------
# game of life loop (main programm)
# -----------------------------------------------------------------------------

  ITERATION=0
  while [ true ]
    do

    # screen output
    (
    echo "Iteration: $ITERATION / $MAXITERATIONS"
    echo
    cat $TEMPFILE
    echo
    echo "CTRL-C to exit"
    ) > $TEMPFILE2
    if [ $USEANSICOLOR -eq 1 ]; then perl -pi -e 's/(X+)/\033[1;31m\1\033[0m/g' $TEMPFILE2; fi
    clear
    cat $TEMPFILE2


    # savefile output
    if [[ "$SAVEFILE" != '' ]]
      then
      (
      echo "clear"
      cat $TEMPFILE2 | perl -pe "s/^(.*)$/echo \"\1\"/g"
      echo "sleep $SAVEFILEDELAY"
      echo
      ) >> $SAVEFILE
      fi


    # end if max iterations reached
    if [ "$ITERATION" -ge "$MAXITERATIONS" ]; then echo "Exit: Max iterations reached."; exit 0; fi

    # end if all is empty
    if [ $(cat $TEMPFILE | grep -c -E "[^\.]") -eq 0 ]; then echo "Exit: Empty field detected."; exit 0; fi

    # end if pattern loops
    if [ $LOOPPROTECTION -eq 1 ]
      then
      LOOPLOG[5]=${LOOPLOG[4]}
      LOOPLOG[4]=${LOOPLOG[3]}
      LOOPLOG[3]=${LOOPLOG[2]}
      LOOPLOG[2]=${LOOPLOG[1]}
      LOOPLOG[1]=$(tr "\n" " " < $TEMPFILE)
      if [[ "${LOOPLOG[1]}" == "${LOOPLOG[2]}" ]]; then echo "Exit: Still life detected."; exit 0; fi
      if [[ "${LOOPLOG[1]}" == "${LOOPLOG[3]}" ]]; then echo "Exit: Oscillator (period 2) detected."; exit 0; fi
      if [[ "${LOOPLOG[1]}" == "${LOOPLOG[4]}" ]]; then echo "Exit: Oscillator (period 3) detected."; exit 0; fi
      if [[ "${LOOPLOG[1]}" == "${LOOPLOG[5]}" ]]; then echo "Exit: Oscillator (period 4) detected."; exit 0; fi
      fi

    # calculate next iteration
    print_next_iteration < $TEMPFILE > $TEMPFILE2
    cat $TEMPFILE2 > $TEMPFILE
    ITERATION=$[$ITERATION+1]

    done
